home *** CD-ROM | disk | FTP | other *** search
/ Aminet 1 (Walnut Creek) / Aminet - June 1993 [Walnut Creek].iso / aminet / dev / misc / psgrind.lha / regexp.c < prev    next >
C/C++ Source or Header  |  1993-04-10  |  15KB  |  643 lines
  1. /*
  2.  * regular expression matching routines for tgrind/tfontedpr.
  3.  *
  4.  * These routines were written by Dave Presotto (I think) for vgrind.
  5.  * Minor mods & attempts to improve performance by Van Jacobson (van@lbl-rtsg)
  6.  * and Chris Torek (chris@maryland).
  7.  *
  8.  * Modifications.
  9.  * --------------
  10.  *  8Apr93 Dylan McNamee  Added support for C++ member function recognization.
  11.  *            Modernized the source code.  Compiles with ANSI
  12.  *            C compiler without warnings now.
  13.  * 30Mar85 Van & Chris    Changed expmatch to return pointer to start of what
  14.  *            was matched in addition to pointer to match end.
  15.  *            Several changes to improve performance (too numerous
  16.  *            to mention).
  17.  * 11Dec84 Dave Presotto  Written.
  18.  */
  19.  
  20. #include <stdlib.h>
  21. #include <string.h>
  22. #include <ctype.h>
  23.  
  24. typedef int    boolean;
  25. #define TRUE    1
  26. #define FALSE    0
  27. #define NIL    0
  28.  
  29. #define makelower(c) (isupper((c)) ? tolower((c)) : (c))
  30.  
  31. extern int (*re_strncmp)(const char *, const char *, size_t);    
  32.                 /* function used by expmatch to compare
  33.                  * strings.  The caller should make it point to
  34.                  * strncmp if case is significant &
  35.                  * lc_strncmp otherwise.
  36.                  */
  37. char   *convexp(char *);
  38. void   expconv(void);
  39. char   *expmatch (char *, char *, char **, char *);
  40. int    lc_strncmp(char *, char *, int);
  41.  
  42. /*  lc_strncmp - like strncmp except that we convert the
  43.  *         first string to lower case before comparing.
  44.  */
  45.  
  46. int
  47. lc_strncmp(s1, s2, len)
  48.     register char *s1,*s2;
  49.     register int len;
  50. {
  51.     while (len-- > 0)
  52.         if (*s2 - makelower(*s1))
  53.             return(1);
  54.         else
  55.         s2++, s1++;
  56.  
  57.     return(0);
  58. }
  59.  
  60. /*    The following routine converts an irregular expression to
  61.  *    internal format.
  62.  *
  63.  *    Either meta symbols (\a \d or \p) or character strings or
  64.  *    operations ( alternation or perenthesizing ) can be
  65.  *    specified.  Each starts with a descriptor byte.  The descriptor
  66.  *    byte has STR set for strings, META set for meta symbols
  67.  *    and OPER set for operations.
  68.  *    The descriptor byte can also have the OPT bit set if the object
  69.  *    defined is optional.  Also ALT can be set to indicate an alternation.
  70.  *
  71.  *    For metasymbols the byte following the descriptor byte identities
  72.  *    the meta symbol (containing an ascii 'a', 'd', 'p', '|', or '(').  For
  73.  *    strings the byte after the descriptor is a character count for
  74.  *    the string:
  75.  *
  76.  *        meta symbols := descriptor
  77.  *                symbol
  78.  *
  79.  *        strings :=    descriptor
  80.  *                character count
  81.  *                the string
  82.  *
  83.  *        operatins :=    descriptor
  84.  *                symbol
  85.  *                character count
  86.  */
  87.  
  88. /*
  89.  *  handy macros for accessing parts of match blocks
  90.  */
  91. #define MSYM(A) (*(A+1))    /* symbol in a meta symbol block */
  92. #define MNEXT(A) (A+2)        /* character following a metasymbol block */
  93.  
  94. #define OSYM(A) (*(A+1))    /* symbol in an operation block */
  95. #define OCNT(A) (*(A+2))    /* character count */
  96. #define ONEXT(A) (A+3)        /* next character after the operation */
  97. #define OPTR(A) (A+*(A+2))    /* place pointed to by the operator */
  98.  
  99. #define SCNT(A) (*(A+1))    /* byte count of a string */
  100. #define SSTR(A) (A+2)        /* address of the string */
  101. #define SNEXT(A) (A+2+*(A+1))    /* character following the string */
  102.  
  103. /*
  104.  *  bit flags in the descriptor 
  105.  */
  106. #define OPT 1
  107. #define STR 2
  108. #define META 4
  109. #define ALT 8
  110. #define OPER 16
  111.  
  112. char *ure;        /* pointer current position in unconverted exp */
  113. char *ccre;        /* pointer to current position in converted exp*/
  114.  
  115. char *
  116. convexp(re)
  117.     char *re;        /* unconverted irregular expression */
  118. {
  119.     register char *cre;        /* pointer to converted regular expression */
  120.  
  121.     /* allocate room for the converted expression */
  122.     if (re == NIL)
  123.     return (NIL);
  124.     if (*re == '\0')
  125.     return (NIL);
  126.     cre = malloc (4 * strlen(re) + 3);
  127.     ure = re;
  128.  
  129.     /* start the conversion with a \a */
  130.     *cre = META | OPT;
  131.     MSYM(cre) = 'a';
  132.     ccre = MNEXT(cre);
  133.  
  134.     /* start the conversion (its recursive) */
  135.     expconv ();
  136.     *ccre = 0;
  137.     return (cre);
  138. }
  139.  
  140. void
  141. expconv()
  142. {
  143.     register char *cs;        /* pointer to current symbol in converted exp */
  144.     register char c;        /* character being processed */
  145.     register char *acs;        /* pinter to last alternate */
  146.     register int temp;
  147.  
  148.     /* let the conversion begin */
  149.     acs = NIL;
  150.     cs = NIL;
  151.     while (*ure != NIL) {
  152.     switch (c = *ure++) {
  153.  
  154.     case '\\':
  155.         switch (c = *ure++) {
  156.  
  157.         /* escaped characters are just characters */
  158.         default:
  159.         if (cs == NIL || (*cs & STR) == 0) {
  160.             cs = ccre;
  161.             *cs = STR;
  162.             SCNT(cs) = 1;
  163.             ccre += 2;
  164.         } else 
  165.             SCNT(cs)++;
  166.         *ccre++ = c;
  167.         break;
  168.  
  169.         /* normal(?) metacharacters */
  170.         case 'a':
  171.         case 'd':
  172.         case 'e':
  173.         case 'p':
  174.         case 'c':
  175.         if (acs != NIL && acs != cs) {
  176.             do {
  177.             temp = OCNT(acs);
  178.             OCNT(acs) = ccre - acs; 
  179.             acs -= temp;
  180.             } while (temp != 0);
  181.             acs = NIL;
  182.         }
  183.         cs = ccre;
  184.         *cs = META;
  185.         MSYM(cs) = c;
  186.         ccre = MNEXT(cs);
  187.         break;
  188.         }
  189.         break;
  190.         
  191.     /* just put the symbol in */
  192.     case '^':
  193.     case '$':
  194.         if (acs != NIL && acs != cs) {
  195.         do {
  196.             temp = OCNT(acs);
  197.             OCNT(acs) = ccre - acs;
  198.             acs -= temp;
  199.         } while (temp != 0);
  200.         acs = NIL;
  201.         }
  202.         cs = ccre;
  203.         *cs = META;
  204.         MSYM(cs) = c;
  205.         ccre = MNEXT(cs);
  206.         break;
  207.  
  208.     /* mark the last match sequence as optional */
  209.     case '?':
  210.         if (cs)
  211.             *cs = *cs | OPT;
  212.         break;
  213.  
  214.     /* recurse and define a subexpression */
  215.     case '(':
  216.         if (acs != NIL && acs != cs) {
  217.         do {
  218.             temp = OCNT(acs);
  219.             OCNT(acs) = ccre - acs;
  220.             acs -= temp;
  221.         } while (temp != 0);
  222.         acs = NIL;
  223.         }
  224.         cs = ccre;
  225.         *cs = OPER;
  226.         OSYM(cs) = '(';
  227.         ccre = ONEXT(cs);
  228.         expconv ();
  229.         OCNT(cs) = ccre - cs;        /* offset to next symbol */
  230.         break;
  231.  
  232.     /* return from a recursion */
  233.     case ')':
  234.         if (acs != NIL) {
  235.         do {
  236.             temp = OCNT(acs);
  237.             OCNT(acs) = ccre - acs;
  238.             acs -= temp;
  239.         } while (temp != 0);
  240.         }
  241.         cs = ccre;
  242.         *cs = META;
  243.         MSYM(cs) = c;
  244.         ccre = MNEXT(cs);
  245.         return;
  246.  
  247.     /* mark the last match sequence as having an alternate */
  248.     /* the third byte will contain an offset to jump over the */
  249.     /* alternate match in case the first did not fail */
  250.     case '|':
  251.         if (acs != NIL && acs != cs)
  252.         OCNT(ccre) = ccre - acs;    /* make a back pointer */
  253.         else
  254.         OCNT(ccre) = 0;
  255.         *cs |= ALT;
  256.         cs = ccre;
  257.         *cs = OPER;
  258.         OSYM(cs) = '|';
  259.         ccre = ONEXT(cs);
  260.         acs = cs;    /* remember that the pointer is to be filles */
  261.         break;
  262.  
  263.     /* if its not a metasymbol just build a scharacter string */
  264.     default:
  265.         if (cs == NIL || (*cs & STR) == 0) {
  266.         cs = ccre;
  267.         *cs = STR;
  268.         SCNT(cs) = 1;
  269.         ccre = SSTR(cs);
  270.         } else
  271.         SCNT(cs)++;
  272.         *ccre++ = c;
  273.         break;
  274.     }
  275.     }
  276.     if (acs != NIL) {
  277.     do {
  278.         temp = OCNT(acs);
  279.         OCNT(acs) = ccre - acs;
  280.         acs -= temp;
  281.     } while (temp != 0);
  282.     }
  283.     return;
  284. }
  285. /* end of convertre */
  286.  
  287.  
  288. /*
  289.  *    The following routine recognises an irregular expresion
  290.  *    with the following special characters:
  291.  *
  292.  *        \?    -    means last match was optional
  293.  *        \a    -    matches any number of characters
  294.  *        \d    -    matches any number of spaces and tabs
  295.  *        \p    -    matches any number of alphanumeric
  296.  *                characters. The
  297.  *                characters matched will be copied into
  298.  *                the area pointed to by 'name'.
  299.  *        \|    -    alternation
  300.  *        \( \)    -    grouping used mostly for alternation and
  301.  *                optionality
  302.  *
  303.  *    The irregular expression must be translated to internal form
  304.  *    prior to calling this routine
  305.  *
  306.  *    The value returned is the pointer to the last character matched.
  307.  *    If strtptr is non-null, a pointer to the start of the string matched
  308.  *    (excluding \a matches) will be returned at *strtptr.  
  309.  *    If mstring is non-null, the string matched by a \p will be copied
  310.  *    into mstring.
  311.  */
  312.  
  313. boolean rescaped;        /* true if we are currently rescaped */
  314. char *rstart;            /* start of string */
  315.  
  316. char *
  317. expmatch (s, re, strtptr, mstring)
  318.     register char *s;        /* string to check for a match in */
  319.     register char *re;        /* a converted irregular expression */
  320.     char **strtptr;        /* where to put ptr to start of match */
  321.     char *mstring;        /* where to put whatever matches a \p */
  322. {
  323.     register char *cs;        /* the current symbol */
  324.     register char *ptr, *s1;    /* temporary pointer */
  325.     register char c;        /* temporary */
  326.     boolean matched;        /* a temporary boolean */
  327.  
  328.     /* initial conditions */
  329.     if ( strtptr )
  330.     *strtptr = NIL;
  331.     if (re == NIL)
  332.     return (NIL);
  333.     cs = re;
  334.     matched = FALSE;
  335.  
  336.     /* loop till expression string is exhausted (or at least pretty tired) */
  337.     while (*cs) {
  338.     switch (*cs & (OPER | STR | META)) {
  339.  
  340.     /* try to match a string */
  341.     case STR:
  342.         matched = !((*re_strncmp)(s, SSTR(cs), SCNT(cs)));
  343.         if (matched) {
  344.  
  345.         /* hoorah it matches */
  346.         s += SCNT(cs);
  347.         cs = SNEXT(cs);
  348.         } else if (*cs & ALT) {
  349.  
  350.         /* alternation, skip to next expression */
  351.         cs = SNEXT(cs);
  352.         } else if (*cs & OPT) {
  353.  
  354.         /* the match is optional */
  355.         cs = SNEXT(cs);
  356.         matched = 1;        /* indicate a successful match */
  357.         } else {
  358.  
  359.         /* no match, error return */
  360.         return (NIL);
  361.         }
  362.         break;
  363.  
  364.     /* an operator, do something fancy */
  365.     case OPER:
  366.         switch (OSYM(cs)) {
  367.  
  368.         /* this is an alternation */
  369.         case '|':
  370.         if (matched)
  371.  
  372.             /* last thing in the alternation was a match, skip ahead */
  373.             cs = OPTR(cs);
  374.         else
  375.  
  376.             /* no match, keep trying */
  377.             cs = ONEXT(cs);
  378.         break;
  379.  
  380.         /* this is a grouping, recurse */
  381.         case '(':
  382.         ptr = expmatch (s, ONEXT(cs), strtptr, mstring);
  383.         if (ptr != NIL) {
  384.  
  385.             /* the subexpression matched */
  386.             matched = 1;
  387.             s = ptr;
  388.         } else if (*cs & ALT) {
  389.  
  390.             /* alternation, skip to next expression */
  391.             matched = 0;
  392.         } else if (*cs & OPT) {
  393.  
  394.             /* the match is optional */
  395.             matched = 1;    /* indicate a successful match */
  396.         } else {
  397.  
  398.             /* no match, error return */
  399.             return (NIL);
  400.         }
  401.         cs = OPTR(cs);
  402.         break;
  403.         }
  404.         break;
  405.  
  406.     /* try to match a metasymbol */
  407.     case META:
  408.         switch (MSYM(cs)) {
  409.  
  410.         /* try to match anything and remember what was matched */
  411.         case 'p':
  412.         /*
  413.          *  This is really the same as trying the match the
  414.          *  remaining parts of the expression to any subset
  415.          *  of the string.
  416.          */
  417.         s1 = s;
  418.         do {
  419.             ptr = expmatch (s1, MNEXT(cs), strtptr, mstring);
  420.             if (ptr != NIL && s1 != s) {
  421.  
  422.             /* we have a match, remember the match */
  423.             if ( mstring ) {
  424.                 strncpy (mstring, s, s1 - s);
  425.                 mstring[s1 - s] = '\0';
  426.             }
  427.             return (ptr);
  428.  
  429.             } else if (ptr != NIL && (*cs & OPT)) {
  430.  
  431.             /* \p was optional so no match is ok */
  432.             return (ptr);
  433.  
  434.             } else if (ptr != NIL) {
  435.  
  436.             /* not optional and we still matched */
  437.             return (NIL);
  438.             }
  439.             if (!isalnum(*s1) && *s1 != '_')
  440.             return (NIL);
  441.             if (*s1 == '\\')
  442.             rescaped = rescaped ? FALSE : TRUE;
  443.             else
  444.             rescaped = FALSE;
  445.         } while (*s1++);
  446.         return (NIL);
  447.         /* try to match C++ anythings and remember what was matched */
  448.         case 'c':
  449.         /*
  450.          *  This is really the same as trying the match the
  451.          *  remaining parts of the expression to any subset
  452.          *  of the string.
  453.          */
  454.         s1 = s;
  455.         do {
  456.             ptr = expmatch (s1, MNEXT(cs), strtptr, mstring);
  457.             if (ptr != NIL && s1 != s) {
  458.  
  459.             /* we have a match, remember the match */
  460.             if ( mstring ) {
  461.                 strncpy (mstring, s, s1 - s);
  462.                 mstring[s1 - s] = '\0';
  463.             }
  464.             return (ptr);
  465.  
  466.             } else if (ptr != NIL && (*cs & OPT)) {
  467.  
  468.             /* \p was optional so no match is ok */
  469.             return (ptr);
  470.  
  471.             } else if (ptr != NIL) {
  472.  
  473.             /* not optional and we still matched */
  474.             return (NIL);
  475.             }
  476.             /* the following define what's "ok" in a member function
  477.              * name -- messy stuff compared to C 
  478.              */
  479.             if (!isalnum(*s1) && *s1 != '_' && *s1 != ':' && 
  480.             *s1 != '~' && *s1 != '=' && *s1 != '>' && *s1 != '<' &&
  481.             *s1 != '+' && *s1 != '-' && *s1 != '&' && *s1 != '|' &&
  482.             *s1 != '*' && *s1 != '/' && *s1 != '^' && *s1 != '%' &&
  483.             *s1 != ',')
  484.             return (NIL);
  485.             if (*s1 == '\\')
  486.             rescaped = rescaped ? FALSE : TRUE;
  487.             else
  488.             rescaped = FALSE;
  489.         } while (*s1++);
  490.         return (NIL);
  491.  
  492.         /* try to match anything */
  493.         case 'a':
  494.         /*
  495.          *  This is really the same as trying the match the
  496.          *  remaining parts of the expression to any subset
  497.          *  of the string.
  498.          */
  499.         s1 = s;
  500.         do {
  501.             /*
  502.              * Hack for an important special case:  if the next thing
  503.              * in the pattern is a string, just gobble characters until
  504.              * we find something that matches that string (this saves
  505.              * the cost of a recursive call on expmatch while scanning
  506.              * for the start of comments or strings).  Since many
  507.              * patterns end with a string, we also treat that as a
  508.              * special case.
  509.              */
  510.             if( *(ptr=MNEXT(cs)) == STR ) {
  511.             c = *SSTR(ptr);
  512.             while( *s1 && *s1 != c )
  513.                 s1++;
  514.  
  515.             if ( *s1 == 0 )
  516.                 return(NIL);
  517.  
  518.             if ( SNEXT(ptr) == 0 && (s1 != s || *cs & OPT)) {
  519.                 /* next item is a string, it's the last item and
  520.                  * the \a match is ok - just loop to try & match
  521.                  * the string.
  522.                  */
  523.                 if ( strtptr )
  524.                 *strtptr = s1;
  525.                 break;
  526.             }
  527.             }
  528.             ptr = expmatch (s1, MNEXT(cs), strtptr, mstring);
  529.             if (ptr != NIL && (s1 != s || *cs & OPT)) {
  530.  
  531.             /* we have a match */
  532.             if ( strtptr )
  533.                 *strtptr = s1;
  534.  
  535.             return(ptr);
  536.  
  537.             } else if (ptr != NIL) {
  538.  
  539.             /* not optional and we still matched */
  540.             return (NIL);
  541.             }
  542.             if (*s1 == '\\')
  543.             rescaped = rescaped ? FALSE : TRUE;
  544.             else
  545.             rescaped = FALSE;
  546.         } while (*s1++);
  547.         return (NIL);
  548.  
  549.         /* fail if we are currently rescaped */
  550.         case 'e':
  551.         if (rescaped)
  552.             return(NIL);
  553.         cs = MNEXT(cs); 
  554.         break;
  555.  
  556.         /* match any number of tabs and spaces */
  557.         case 'd':
  558.         ptr = s;
  559.         while (*s == ' ' || *s == '\t')
  560.             s++;
  561.         if (s != ptr || s == rstart) {
  562.  
  563.             /* match, be happy */
  564.             matched = 1;
  565.             cs = MNEXT(cs); 
  566.         } else if (*s == '\n' || *s == '\0') {
  567.  
  568.             /* match, be happy */
  569.             matched = 1;
  570.             cs = MNEXT(cs); 
  571.         } else if (*cs & ALT) {
  572.  
  573.             /* try the next part */
  574.             matched = 0;
  575.             cs = MNEXT(cs);
  576.         } else if (*cs & OPT) {
  577.  
  578.             /* doesn't matter */
  579.             matched = 1;
  580.             cs = MNEXT(cs);
  581.         } else
  582.  
  583.             /* no match, error return */
  584.             return (NIL);
  585.         break;
  586.  
  587.         /* check for end of line */
  588.         case '$':
  589.         if (*s == '\0' || *s == '\n') {
  590.  
  591.             /* match, be happy */
  592.             s++;
  593.             matched = 1;
  594.             cs = MNEXT(cs);
  595.         } else if (*cs & ALT) {
  596.  
  597.             /* try the next part */
  598.             matched = 0;
  599.             cs = MNEXT(cs);
  600.         } else if (*cs & OPT) {
  601.  
  602.             /* doesn't matter */
  603.             matched = 1;
  604.             cs = MNEXT(cs);
  605.         } else
  606.  
  607.             /* no match, error return */
  608.             return (NIL);
  609.         break;
  610.  
  611.         /* check for start of line */
  612.         case '^':
  613.         if (s == rstart) {
  614.  
  615.             /* match, be happy */
  616.             matched = 1;
  617.             cs = MNEXT(cs);
  618.         } else if (*cs & ALT) {
  619.  
  620.             /* try the next part */
  621.             matched = 0;
  622.             cs = MNEXT(cs);
  623.         } else if (*cs & OPT) {
  624.  
  625.             /* doesn't matter */
  626.             matched = 1;
  627.             cs = MNEXT(cs);
  628.         } else
  629.  
  630.             /* no match, error return */
  631.             return (NIL);
  632.         break;
  633.  
  634.         /* end of a subexpression, return success */
  635.         case ')':
  636.         return (s);
  637.         }
  638.         break;
  639.     }
  640.     }
  641.     return (s);
  642. }
  643.